#include <stdlib.h>
#include <sys/param.h> // for MIN/MAX
#include <string.h>
#include <assert.h>
#include "rect.h"

// Cuts a Rect into 4 pieces by cutting out another rect in the middle of it
// Resulting pieces might be invalid Rects, for example orig.left might be
// greater than pieces[i].left
// The two rects must exist on the same layer!
inline void cut_rect (const Rect* orig, const Rect* cutout, Rect (*pieces) [4])
{
	assert (orig->z == cutout->z);
	(*pieces) [0] = (Rect) { orig->left, orig->top, cutout->left, orig->bottom, orig->z };
	(*pieces) [1] = (Rect) { cutout->right, orig->top, orig->right, orig->bottom, orig->z };
	(*pieces) [2] = (Rect) { orig->left, orig->top, orig->right, cutout->top, orig->z };
	(*pieces) [3] = (Rect) { orig->left, cutout->bottom, orig->right, orig->bottom, orig->z };
}

// Take a list of rects and cut all of them with cut_rect. Rearrange the resulting pieces
// back into the list and always keep the largest area Rect at the front.
// keep only those rects including inc_x/inc_y
void cut_all_rects (RectList* list, const Rect* cutout, int inc_x, int inc_y)
{
	Rect cutresult [RECTLIST_MAX*4];
	int num_result = 0;
	Rect pieces[4];

	if (list == NULL) return;

	inline int rect_valid (Rect* r) { return (r->bottom - r->top >= 3) && (r->right - r->left >= 3); }

	for ( int i = 0; i < list->num_rects; i++) {
		if (rect_intersect_rect(&list->rect[i], cutout)) {
			cut_rect (&list->rect[i], cutout, &pieces);
			for (int j = 0; j < 4; j++) {
				Rect* r = &pieces[j];
				if (point_in_rect (r, inc_x, inc_y, cutout->z) && rect_valid (r)) {
					cutresult [num_result++] = *r;
				}
			}
		} else {
			cutresult [num_result++] = list->rect[i];
		}
	}

	int area_compare (const void* p1, const void* p2)
	{
		const Rect* r1 = (const Rect*) p1;
		const Rect* r2 = (const Rect*) p2;
		return (r2->bottom - r2->top) * (r2->right - r2->left) - (r1->bottom - r1->top) * (r1->right - r1->left);
	}

	qsort(cutresult, num_result, sizeof(Rect), &area_compare);
	num_result = MIN (num_result, RECTLIST_MAX);
	memcpy (list->rect, cutresult, sizeof (Rect) * num_result);
	list->num_rects = num_result;
}

int point_in_rect (const Rect* r, int x, int y, int z)
{
	return (z == r->z) && (x >= r->left) && (y >= r->top) && (x < r->right) && (y < r->bottom);
}

int rect_intersect_rect (const Rect* r1, const Rect* r2)
{
	if (r1->z != r2->z) return 0;
	return (r1->right > r2->left) && (r1->bottom > r2->top) && (r1->left < r2->right) && (r1->top < r2->bottom);
}

coord_t rect_middle (Rect* r)
{
	return (coord_t) {
		r->left + (r->right - r->left)/2,
		r->top + (r->bottom - r->top)/2,
		r->z
	};
}
